package com.changanw.code23;



import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Queue;

/**
 * @author changanw
 * @description 合并 K 个升序链表
 * @date 2023/7/13 22:37
 */
public class Code23 {
  public ListNode mergeKLists(ListNode[] lists) {
    ListNode ans = null;
    for (int i = 0; i < lists.length; ++i) {
      ans = mergeTwoLists(ans, lists[i]);
    }
    return ans;
  }
  public ListNode mergeKLists2(ListNode[] lists){
    /**
     *ListNode l1 = new ListNode(1,new ListNode(4,new ListNode(5)));
     *ListNode l2 = new ListNode(2,new ListNode(6));
     * -1 1 4 5
     * -1 1 2 6
     * -1 1 2 4 5
     * -1 1 2 4 5 6
     */
    // 添加一个虚拟头节点（哨兵），帮助简化边界情况的判断
    ListNode dummyHead = new ListNode(-1);
    Queue<ListNode> pq = new PriorityQueue<>(Comparator.comparingInt(v -> v.val));
    for (ListNode list : lists) {
      if (list != null){
        pq.offer(list);
      }
    }
    // 合并成功之后的尾节点位置
    ListNode tail = dummyHead;
    while (!pq.isEmpty()){
      ListNode minNode = pq.poll();
      // 把这个节点连接到合并链表的尾部
      tail.next = minNode;

      // tail 的位置也随之发生变化
      tail = minNode;

      // PriorityQueue 实现了 Queue 接口，不允许放入 null 元素
      if (minNode.next != null) {
        // 再把新的节点也加入到优先队列当中
        pq.offer(minNode.next);
      }
    }
    return dummyHead.next;

  }

  //合并两个有序链表
  public ListNode mergeTwoLists(ListNode a, ListNode b) {
    if (a == null || b == null) {
      return a != null ? a : b;
    }
    ListNode head = new ListNode(0);
    ListNode tail = head, aPtr = a, bPtr = b;
    while (aPtr != null && bPtr != null) {
      if (aPtr.val < bPtr.val) {
        tail.next = aPtr;
        aPtr = aPtr.next;
      } else {
        tail.next = bPtr;
        bPtr = bPtr.next;
      }
      tail = tail.next;
    }
    tail.next = (aPtr != null ? aPtr : bPtr);
    return head.next;
  }


  public static void main(String[] args) {
    ListNode l1 = new ListNode(1,new ListNode(4,new ListNode(5)));
    ListNode l2 = new ListNode(2,new ListNode(6));
    ListNode l3 = new ListNode(1,new ListNode(3,new ListNode(4)));
    List<ListNode> param = new ArrayList<>();
    param.add(l1);
    param.add(l2);
    //param.add(l3);
    Code23 code23 = new Code23();
    ListNode listNode = code23.mergeKLists2(param.toArray(param.toArray(new ListNode[0])));
    System.out.println(listNode.val);
  }




  static class ListNode {
    int val;
    ListNode next;

    ListNode() {
    }

    ListNode(int val) {
      this.val = val;
    }

    ListNode(int val, ListNode next) {
      this.val = val;
      this.next = next;
    }
  }
}
